Before the explanation of the invention, let's explain a little bit about the M-sequence.
M-sequence, which is the abbreviation of maximum length sequence, is defined as the sequence {a.sub.i } which is generated by a shift register circuit with a certain feedback as shown in FIG. 3. The M-sequence can be generated from the equation a.sub.i+n. Although there exists a multi-level M-sequence, the M-sequence, widely used is of two-levels having either 0 or 1; in FIG. 3, h.sub.i =0 or 1 and a.sub.i =0 or 1. We consider hereafter only the two-level M-sequence unless otherwise stated. M-sequence has the following properties:
(1) The period is 2.sup.n -1 (n=1,2, . . . ), where n is the number of the stages of the shift register. PA0 (2) Every possible n-tuple except all zero appears exactly once in a period. That is, when we take an n-tuple (a.sub.i, a.sub.i+1, . . . a.sub.i+n-1)(i=0,1, . . . ,2.sup.n -2), every possible n-tuple except an all zero pattern appears once and only once in a period. So when the content of the n-tuple is considered to be a binary number, all integers except zero from 1 to 2.sup.n -1 appear once in a period. PA0 (3) In a period 2.sup.n -1, there are 2.sup.n-1 -1 zeros and 2.sup.n-1 ones. That is, the number of ones and zeros in a period is nearly equal. This invention uses the property (1) and (2) together with the two dimensional property of M-sequence when the M-sequence is arranged in two dimensional fashion.
Now, the outline of the detection method of pattern-sensitive-faults is described. FIG. 1 shows a two-dimensional array of a memory where B denotes the cell under consideration (called base cell). The neighboring cells are denoted as N,S,W,E. The pattern-sensitive-fault is such a fault as the content of cell B, originally supposed to be 0 (or 1), changes to 1 (or 0) when the content of NSWE is, say 1110. In order to detect PSF, it is necessary to check if the content of B is changed for all 16 patterns of neighboring cells NSWE from 0000 to 1111. Various researchers have tried to find some method for PSF detection as to what kind of sequences should be used and how the sequence are used for writing each memory cell effectively. However, those previous methods are very complicated from the point of view of algorithm and are not suited for built in test. This invention covers those defects by use of pseudorandom M-sequence.